﻿#define _CRT_SECURE_NO_WARNINGS 1

//动态规划第八题
//931. 下降路径最小和
//https://leetcode.cn/problems/minimum-falling-path-sum/description/

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        // 状态表示
        // dp[i][j] 表示某个位置的最小和。
        vector<vector<int>> dp(m + 1, vector<int>(m + 2, INT_MAX));

        // 初始化第一行
        for (int j = 1; j <= m; j++) {
            dp[0][j] = 0;
        }

        // 填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] =
                    min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) +
                    matrix[i - 1][j - 1];
            }
        }
        int M = INT_MAX;

        for (int j = 1; j <= m; j++) {
            M = min(M, dp[m][j]);
        }

        return M;
    }
};